package com.lw.test;

/**
 * Created with IntelliJ IDEA.
 * 二分法模板
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/7 10:19
 */
public class Binary {

    /**
     * 二分法一共三种形式
     * 1：在一个有序不重复的数组中，查找目标值，若存在，返回索引下标，若不存在，返回 -1。
     * 2：在一个有序可重复的数组中，查找小于目标值的最大值，若存在，返回索引下标，若不存在，返回 -1。
     * 3：在一个有序可重复的数组中，查找大于目标值的最小值，若存在，返回索引下标，若不存在，返回 -1。
     */

    /**
     * 需要注意的几个地方：
     * 1：除以2的时候，可以用位运算，提高效率。 比如 /2 用 >> 1 代替， 同理 /4 用 >> 2 代替。
     * 2：求中点 m  的时候，不能用  (st + end) / 2， 防止 int 型的数据类型溢出。可以用 m = st + ((end - st) >> 1) 代替。
     * 3：小于target的最大值， 求m向上取整， m = st + ((end - st + 1) >> 1)
     */

    /**
     * 练习：
     * （1）35. 搜索插入位置：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
     *      如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     *      请必须使用时间复杂度为 O(log n) 的算法。
     *
     * （2）34. 在排序数组中查找元素的第一个和最后一个位置：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     *      如果数组中不存在目标值 target，返回 [-1, -1]。
     *
     * （3）69. x 的平方根：实现 int sqrt(int x) 函数。
     *      计算并返回 x 的平方根，其中 x 是非负整数。
     *      由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
     */

    /**
     * 查找目标值
     *
     * @param nums   数组
     * @param target 目标值
     * @return 索引下标
     */
    public int binary1(int[] nums, int target) {
        int st = 0;
        int end = nums.length - 1;
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            if (nums[m] < target) {
                st = m + 1;
            } else if (nums[m] > target) {
                end = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 小于target的最大值
     *
     * @param nums   数组
     * @param target 目标值
     * @return 索引下标
     */
    public int binary2(int[] nums, int target) {
        if (nums[0] >= target) {
            return -1;
        }
        int st = 0;
        int end = nums.length - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums[m] < target) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

    /**
     * 大于target的最小值
     *
     * @param nums   数组
     * @param target 目标值
     * @return 索引下标
     */
    private int binary3(int[] nums, int target) {
        int end = nums.length - 1;
        if (nums[end] <= target) {
            return -1;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (nums[m] > target) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

}
